package com.nowcoder.code.lcof;

public class JZ47 {

    public static void main(String[] args) {

        System.out.println(new JZ47().maxValue(new int[][]{
                {1,3,1},
                {1,5,1},
                {4,2,1}
        }));

    }

    public int maxValue(int[][] grid) {
        return dfs(grid, 0, 0);
    }


    public int dfs(int[][] grid, int i, int j) {
        if (i >= grid.length || i < 0 || j >= grid[i].length || j < 0) {
            return 0;
        }
        if (grid[i][j] < 0) {
            return -grid[i][j];
        }
        int max = grid[i][j] + Math.max(dfs(grid, i + 1, j), dfs(grid, i, j + 1));
        grid[i][j] = -max;
        return max;
    }

}
